package DFS递归搜索与回溯.递归;

/**
 * 两两交换链表中的节点
 */
public class ListNode {

    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    // 两两交换节点中的位置
    public ListNode swapPairs(ListNode head) {
        // 空或者是只有一个节点, 用不了两两翻转. 因为两两翻转必须得是两个
        if(head == null || head.next == null) return head;

        // 注意是两个 next
        // ListNode tmp = swapPairs(head.next);
        ListNode tmp = swapPairs(head.next.next);
        ListNode headNext = head.next;
        // 把头结点连接到反转后的链表上
        head.next = tmp;
        headNext.next = head;

        return headNext;
    }

    // k个一组进行翻转, 对比着翻转两个链表的来写

    public ListNode reverseKGroup(ListNode head, int k) {
        //退出递归的条件
        if(head == null ) return head;
        ListNode tail = head;
        for(int i =0;i<k;i++){
            // if(tail == null) break; // 这个是不足k也反转
            if(tail == null) return head; // 不足k的节点，保持原来顺序
            tail = tail.next;
        }
        //反转前k个节点
        ListNode newHead = reverse(head, tail);
        //下一轮的开始还是tail节点，因为你是要确定下一次返回链表的头节点的位置
        head.next =  reverseKGroup(tail,k);
        return newHead;
    }
    public ListNode reverse(ListNode head, ListNode tail){
        ListNode prev =null;
        ListNode cur = head;
        //只需要把原来判断尾节点为空的，改为在传入节点就行。
        while(cur !=tail){
            ListNode next = cur.next;
            cur.next = prev;
            prev =cur;
            cur = next;
        }
        return prev;
    }

    // todo 自己写的正确版本
    public ListNode reverseKGroup3(ListNode head, int k) {
            // 少于 k 个链表的直接返回. 不用翻转(根据题目要求)
            // if(head == null) return head;
            // ListNode cur = head;
            // int count = 0;
            // while(cur != null) {
            //     cur = cur.next;
            //     count++;
            // }
            // if(count < k) return head;

            // cur = head;
            // for (int i = 0; i < k; i++) {
            //     cur = cur.next;
            // }

            //退出递归的条件. 也可以用上一个代替
            if(head == null ) return head;
            ListNode tail = head;
            for(int i =0;i<k;i++){
                // if(tail == null) break; // 这个是不足k也反转
                if(tail == null) return head; // 不足k的节点，保持原来顺序
                tail = tail.next;
            }

            // dfs 主逻辑
            // ListNode tmp = reverseKGroup(cur, k);
            ListNode tmp = reverseKGroup(tail, k);
            // 把前k个进行翻转然后链接到后面
            ListNode cur = head;
            ListNode tmp2 = head; // 记录用于标记下一次头插的地方. 也就是反转之后的尾节点
            ListNode prev = new ListNode();
            int ret = k;
            while (ret-- != 0) {
                ListNode curNext = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = curNext;
            }
            // todo 找到反转之后的尾节点.  可以用一个变量提前进行标记
            // 再次找到 k 个之后的节点
            // cur = head;
            // ret = k;
            // while(ret-- != 1) {
            //     cur = cur.next;
            // }
            // cur.next = tmp;
            tmp2.next = tmp;
            return prev.next;
    }

    // todo 错误版本
    public ListNode reverseKGroup2(ListNode head, int k) {
        // 少于 k 个链表的直接返回. 不用翻转(根据题目要求)
        if(head == null) return head;
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        if(count < k) return head;

        cur = head;
        for (int i = 0; i < k; i++) {
            cur = cur.next;
        }
        // dfs 主逻辑
        ListNode tmp = reverseKGroup2(cur, k);
        // 把前k个进行翻转然后链接到后面
        cur = head;
        ListNode prev = null;
        int ret = k;
        while (ret-- != 0) {
            ListNode curNext = cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = curNext;
        }
        // 再次找到 k 个之后的节点
        cur = head;
        ret = k;
        while(ret-- != 0) {
            cur = cur.next;
        }
        cur.next = tmp;
        return prev.next;
    }

}
